//使用嵌套类实现一个模板类---队列
//嵌套类是在另一个类中声明的类
#ifndef QUEUETP_H_
#define QUEUETP_H_
#include <iostream>

//模板类
template<class Item>
class QueueTP
{
private:
	enum{Q_SIZE=10};
	//嵌套类，声明为私有成员时，外界和派生类不知道Node的存在
	class Node
	{
	public:
		Item item;
		Node* next;
		Node(const Item& i) :item(i), next(0) {}

	};
	Node* front;	//队头指针
	Node* rear;		//队尾指针
	int items;		//队列长度
	const int qsize;
	QueueTP(const QueueTP& q) :qsize(0) {}
	QueueTP& operator=(const QueueTP& q) { return *this; }
public:
	QueueTP(int qs = Q_SIZE);
	~QueueTP();

	bool isempty() const
	{
		return items==0;
	}


	bool isfull() const
	{
		return (items == qsize);
	}


	int queuecount() const
	{
		return items;
	}


	bool enqueue(const Item& item);	//在队尾入队
	bool dequeue(Item& item);		//对头出队


};

//队列方法实现

template<class Item>
QueueTP<Item>::QueueTP(int qs) :qsize(qs)	//创建一个队列
{
	front = rear = nullptr;
	items = 0;
}

template<class Item>
QueueTP<Item>::~QueueTP()	//删除一整条队列：将所有结点全部delete
{
	//如果从队尾删除，没有办法去前一个结点（只有next）
	//故从队头开始删除
	Node* temp;
	while (front != 0)
	{
		temp = front;
		front = front->next;
		delete temp;
	}
}

//从队尾加入
template<class Item>
bool QueueTP<Item>::enqueue(const Item& item)	
{
	if (isfull())
	{
		std::cout << "full!" << std::endl;
		return false;
	}
	
	Node* add = new Node(item);
	//items++原来在这里


	//先看队列是否为空
	//问题：如果使用isempty()来判断，程序会崩溃！！	
	// 答：看items++原来的位置，在enqueue中，items在插入之前就已经加加，那么在插入到空队列时，在真正插入的时候items实际==1！！！，导致执行了else的内容:访问了不存在的rear->next导致程序崩溃
	if (isempty())
		front = add;
	else
		rear->next = add;
	rear = add;	//怎么都要执行
	items++;//改进后的顺序是在真正插入队列后才items++，防止了对空队列判断的判断失误
	std::cout << "enqueued!" << std::endl;
	return true;
}

//从队头删除,并将队头元素赋值给item
template<class Item>
bool QueueTP<Item>::dequeue(Item& item)
{
	if (isempty())			//用front==0判断还是isempty()
	{
		std::cout << "empty!" << std::endl;
		return false;
	}
	item = front->item;
	Node* temp = front;
	front = front->next;
	delete temp;
	items--;
	//若队列为空
	if (isempty())			//这里也是，用isempty()还是items==0
		rear = nullptr;
	return true;
}



//队列方法的注意事项：无论是删除还是增加结点，都要考虑下队列是否空或满
/*
增加结点时：
	1.要先判断队列是否满了
	2.如果队列为空，要将front指针指向新结点，rear无论如何都会指向新结点
删除结点时：
	1.要先判断队列是否为空
	2.如果队列为空，要将rear指针指向nullptr，front会指向下一个结点（或是nullptr）
小细节：items++必须放到真正插入的操作后，否则应该用front==nullptr来判断队列是否为空
*/

#endif